1. Field of the Subject Matter
The present disclosure generally relates to multipath computer networks and, more specifically, to methods, a system and apparatuses that manage traffic flow through a multiple path network.
2. Background Information
In computer network implementations, data may be transferred in packets between a source device and a destination device via one or more routers. In some cases, routers may include multiple ports such that packets may follow alternative paths to a destination device. Such a configuration is referred to herein as a “multipath network” and may generally refer to a network that has multiple media channels (including wired and wireless channels), multiple routes (such as those generated by a multipath routing protocol), or redundant links between a source and a destination. Traffic partitioning in multipath networks may, in some embodiments, be accomplished by dynamically distributing packets across routers. In one example of dynamic distribution of network traffic, the path loads within the network may govern the assignment of a data packet to a path. More specifically, a data packet may be forwarded along a path with the smallest load. Such a load balancing technique, however, may cause path oscillation (i.e., delivering packets of the same stream on different paths). Packets traveling from the same source to the same destination may generally be referred to herein as members of the same address flow or the same stream. In some cases, path oscillation causes packets of the same stream to be delivered to the destination address out of order. In such a case, the receipt of data at the destination device may be delayed relative to if the stream was delivered sequentially over the same path since the packets have to be reordered prior to being received at the destination address.
Other manners for dynamically partitioning network traffic include recording path assignments in individual routers or within the packet's header and adjusting the assignment as needed for load balancing. Such techniques may reduce path oscillation relative to the method described above in which path loads are used to govern the path assignment of a data packet. The method of storing path assignments or any additional information within a packet's header is sometimes referred to as packet tagging. Such a method may increase the processing time per packet within the routers, causing loads of the routers to increase relative to embodiments in which the path assignment is not recorded within the packet header. In addition, such a method involves multiple routers agreeing on the meaning of the recorded path assignments. Consequently, there is a setup cost associated with this method. The method of recording path assignments at each router, however, may entail the routers to store the status of each flow, which is sometimes referred to as “per-flow state-maintenance.” A large amount of memory is needed for each router in such a method and, as a result, the number of flows per router is limited.
In some cases, the technique in which path assignments are determined at individual routers may be altered slightly by grouping flows into buckets according to their hashed addresses, where the number of buckets is smaller than the number of flows, but larger than the number of paths. The router maintains the path assignment for each bucket rather than for each flow, providing a coarser granularity than maintaining path assignments per flow. When path loads are unbalanced, at least one bucket of flows is moved across routes in order to rebalance the paths. A large number of buckets allows for fine-grained load balance but requires more memory and more computation, while a small number of buckets may not be effective in reducing path oscillation, especially if buckets are unevenly loaded. Consequently, such a technique includes some drawbacks with regard to the number of buckets selected to group the flows. In addition, when traffic patterns change, it might be necessary to reset the number of buckets accordingly. This is undesirable since resetting the numbers of buckets increases the burden on network management.
Regardless of the technique used, dynamic partitioning may, in some embodiments, reduce bandwidth on Transmission Control Protocol (TCP) connections. TCP is the protocol for the majority of traffic on the Internet and private networks and uses a congestion window to limit how fast the sender can inject packets into the network. In general, a network with larger capacity or less congestion will produce a larger window size, which allows higher sending bandwidth. If packets in the same TCP connection are transmitted over paths of different loss rates, the resulting bandwidth may reflect the highest loss rate rather than take advantage of the bandwidth available in lower-loss paths. Therefore, due to loss rate variation as well as out-of-order delivery, TCP traffic may not be able to consume the bandwidth otherwise made available by multipath networking when dynamic partitioning is employed.
As such, it would be advantageous to develop systems, apparatuses and methods for improving bandwidth utilization for Transmission Control Protocol (TCP) connections on multipath networks. In addition, it would be advantageous to develop systems, apparatuses and methods for distributing data packets on multipath networks that allow for fine-grained load balancing. Moreover, it would be beneficial for such system, apparatuses and methods to be configured to preserve a path for packets within the same flow as long as load balancing permits. In cases of unbalanced loads, however, it would be desirable for the system, apparatuses and methods to switch only a minimal amount of traffic between paths. In addition, it may be advantageous to develop system, apparatuses and methods of partitioning flows which do not require per-flow state-maintenance or packet tagging.